package oj;

public class LC148 {
    public ListNode sortList(ListNode head) {
        if(head==null || head.next==null) return head;
        ListNode slow =head;
        ListNode fast=head.next;
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode l2=slow.next;
        slow.next=null;

        ListNode left=sortList(head);
        ListNode right=sortList(l2);

        ListNode dummyHead=new ListNode(0);
        ListNode h=dummyHead;
        while(left!=null && right!=null){
            if(left.val<=right.val){
                h.next=left;
                left=left.next;
            }else{
                h.next=right;
                right=right.next;
            }
            h=h.next;
        }
        h.next=left!=null?left:right;
        return dummyHead.next;
    }
}
